package 程序员面试金典;

/**
 * 面试题 02.05. 链表求和
 * 给定两个用链表表示的整数，每个节点包含一个数位。
 *
 * 这些数位是反向存放的，也就是个位排在链表首部。
 *
 * 编写函数对这两个整数求和，并用链表形式返回结果。
 *
 *
 *
 * 示例：
 *
 * 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
 * 输出：2 -> 1 -> 9，即912
 * 进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?
 *
 * 示例：
 *
 * 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
 * 输出：9 -> 1 -> 2，即912
 */
public class T02_05 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        int temp = 0; //表示进位

        ListNode p1 = l1;
        ListNode p2 = l2;

        ListNode preHead = new ListNode(-1);
        ListNode p3 = preHead;


        while (p1 != null && p2 != null) { //其中一个为null 说明有一个走到了结尾

            int val = (p1.val + p2.val + temp) % 10;//确定最终的值

            temp = (p1.val + p2.val + temp) / 10; //进位值

            ListNode listNode = new ListNode(val);
            p3.next = listNode; //插入p3 链表的末尾
            p3 = p3.next;
            p1 = p1.next;
            p2 = p2.next;

        }

        while (p1 != null) {
            int val = (p1.val + temp) % 10;
            temp = (p1.val + temp) / 10;

            ListNode listNode = new ListNode(val);
            p3.next = listNode;
            p3 = p3.next;
            p1 = p1.next;
        }

        while (p2 != null) {
            int val = (p2.val + temp) % 10;
            temp = (p2.val + temp) / 10;
            ListNode listNode = new ListNode(val);
            p3.next = listNode;
            p3 = p3.next;
            p2 = p2.next;
        }

        if (temp > 0) {  //最后还有一个进位值
            ListNode listNode = new ListNode(temp);
            p3.next = listNode;

        }

        return preHead.next; //返回链表的头部

    }

    //链表的定义
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
